\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}
\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}
\mode<article>{\usepackage{fullpage}}

\title{Lecture Six -- Queues and Stacks}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}

\section{Queues}

\mode<presentation>{\begin{frame}
  \frametitle{Two Types of Data Structures}
  \begin{itemize}
    \item FIFO -- First In First Out
    \item LIFO -- Last In First Out 
  \end{itemize}
\end{frame}}

\subsection{Overview}

\mode<presentation>{\begin{frame}
  \frametitle{Two Operations}
  \begin{itemize}
    \item enqueue -- Place item at end of queue
    \item dequeue -- Remove item at front of queue
  \end{itemize}
\end{frame}}

A queue is the FIFO, or first-come-first-served data structure that
we're used to seeing in everyday life (later we'll talk about
\emph{priority queues} where this idea doesn't quite hold).

In an abstract sense, queues usually have a method that allows us to
insert at element at the end or tail of a list (we will call this the
\emph{enqueue} operation) and another method that removes an element
at the front or head of a list (we will call this the \emph{dequeue}
operation).  Many implementations also have a \emph{peek} operation
that returns but does not remove the element at the front or head of a
list.


\subsection{Textbook Implementation: PureQueue}
The book provides a nice interface that it uses to conceptualize the
queue operations:
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Textbook Implementation: PureQueue}}
  \begin{lstlisting}
  public interface PureQueue<E> {
    public int size();
    public boolean isEmpty();
    public void enqueue(E element);
    public E dequeue();
    public E front(); //same as 'peek'
  }
  \end{lstlisting}
  The Java Collections framework provides 
  \href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html}{a queue interface}.
\end{frame}


\subsection{Queue Implementations}
There are many ways to implement a queue, all of which build on top of
data structures we've already seen.  Here, though, we want to pay
special attention to how the implementation details affect the
performance of our queue.

\subsubsection{Dynamic Array Based}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Dynamic Array Based Queue}}
  \begin{itemize}
    \item Insertion: Could be constant time, but worst case is $O(n)$
    \item Removal: $O(n)$
  \end{itemize}
\end{frame}
Here we see that the dynamic array (array list) is a very poor choice
for implementing a queue.  This is beacause though we are able to
easily add items on to one end of the queue, removal from the other
end requires that we re-copy the array (since dynamic arrays keep
their items contiguous).

\subsubsection{LinkedList Based}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Linked List Based Queue}}
  \begin{itemize}
    \item Enqueue: No worse that than $O(n)$, could be $O(1)$
    \item Dequeue: No worse that than $O(n)$, could be $O(1)$
  \end{itemize}
See book example \href{http://www.mhhe.com/engcs/compsci/collins/source_code/ch8/LinkedListQueueMain/LinkedListPureQueue.java}{here}.
\end{frame}
The linked list provides a very natural implmentation of a queue.  To
speed things up, we can keep references to both the head and tail,
thus making the both the enqueue and dequeue operations constant time.

\subsubsection{Circular Arrays}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Circular Array Based Queue}}
  \begin{itemize}
    \item Enqueue: $O(1)$
    \item Dequeue: $O(1)$
  \end{itemize}
\end{frame}
A more unique way to solve this problem is to use an array, but in a
'circular' fashion.  If we think of the end of the array as 'next to'
the start of the array, we can move the head and tail of the queue
down the array, circling back as needed.  Obviously, there are some
limitations here since we need to know the maximum size of the queue
before we start.

\subsection{Queue Applications}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Queue Applications}}
  \begin{itemize}
    \item Round robin DNS
    \item Naive process/thread scheduling
  \end{itemize}
\end{frame}
Anytime you want to use resources in a first come, first served fashion,
you need a queue.  This happens all the time.

\section{Stacks}
\mode<presentation>{\begin{frame}
  \frametitle{Two Operations}
  \begin{itemize}
    \item push -- Place item on top of stack
    \item pop -- Remove item at top of stack
  \end{itemize}
\end{frame}}

Stacks are a LIFO (last in first out) data structure.

The operation that adds an item to the top of the stack is called a
\emph{push} operation.  The operation that removes an item from the top
of the stack is called a \emph{pop} operation.  Again we have the
\emph{peek} operation that returns but does not remove the item at the
top of the stack.

Though the stack may, at first glance, seem like a relatively useless
data structure, quite the opposite is true.  As we've discussed
function calls use a stack all the time.


\subsection{Textbook Implementation: PureStack}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Textbook Implementation: PureStack}}
  \begin{lstlisting}
  public interface PureStack<E> {
    public int size();
    public boolean isEmpty();
    public void push(E element);
    public E pop();
    public E peek();
  }
  \end{lstlisting}
\end{frame}


\subsection{Stack Implementations}

\subsubsection{Array Based}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Array Based Stack}}
  \begin{itemize}
    \item Push: $O(1)$
    \item Pop: $O(1)$
  \end{itemize}
\end{frame}
This is a very typical stack implemenation.  It is easy to implmenent
and fast. Obviously, we have the same problem as the circular queue;
there is an upper size limit on the stack.  Still, there are few
applications where we actually need or want an arbitrarily large
stack.


\subsubsection{Dynamic Array Based}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Dynamic Array Based Stack}}
  \begin{itemize}
    \item Push: perhaps constant time but really $O(n)$ (if array needs to be resized)
    \item Pop: $O(1)$
  \end{itemize}
\end{frame}
This looks just like the array based implementation only without the
inherent size limitation.  The tradeoff is that pushing at item could
be an $O(n)$ operation.  Stacks are not often implemented in this
fashion.

\subsubsection{Linked List Based}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Linked List Based Stack}}
  \begin{itemize}
    \item Push: $O(n)$...could it be $O(1)$?
    \item Pop: $O(n)$...could it be $O(1)$?
  \end{itemize}
\end{frame}
Here we have an arbitrarily large stack, but we can push the two
operations down to constant time if we maintain references to the head
and tail.  Obviously this is the implemenation of choice when an
arbitrarily large stack is required.

\subsection{Stack Applications}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{The Ubiquitous Stack!}}
  \begin{lstlisting}
    main() ...
      startup() ...
        loadfile() ...
          wait_for_disk() ...
  \end{lstlisting}
\end{frame}
Stack are used all the time.  The most ubiquitous example is that of
method or function calls.  Looking at the psuedo code above,
\verb'main()' calls \verb'startup()' and so on. Notice that this is a
LIFO situation.  \verb'wait_for_disk()' was the last function called,
but must be evaluated first since \verb'loadfile()' is waiting for it
to return (this changes somewhat in a language with lazy evaluation,
but we will not consider that at the moment).

\end{document}
